package com.gxc.linkedList;

/**
 * 61. 旋转链表
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 */
public class RotateRight {

    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null) return head;
        int l = 0;
        ListNode node = head;
        ListNode last = head;
        while (node!=null) {
            l++;
            if (node.next != null) last = node.next;
            node = node.next;
        }
        //取余。当k>l的时候
        k = k % l;
        if (k == 0) return head;
        k = l-1-k;
        node = head;
        while (k > 0) {
            node = node.next;
            k--;
        }
        ListNode newHead = node.next;
        last.next = head;
        node.next = null;
        return newHead;
    }

    public ListNode rotateRight2(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        //收尾相连后，减少一个last 节点
        iter.next = head;
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode ret = iter.next;
        iter.next = null;
        return ret;
    }

    public static class ListNode {
        int val;
        RotateRight.ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, RotateRight.ListNode next) { this.val = val; this.next = next; }
    }
}
